﻿//给定一个长度为 n 的正整数数组 coins，每个元素表示对应位置的金币数量。
//取位置i 的金币时，假设左边一堆金币数量是L，右边一堆金币数量为R，则获得L∗cost[i]∗R的积分。
//如果左边或右边没有金币，则金币数量视为1。
//请你计算最多能得到多少积分。
//
//数据范围：数组长度满足1≤n≤100  ，数组中的元素满足1≤coinsi≤100
//
//输入：
//	[5, 6, 4, 8]
//返回值：
//	480
//说明：
//	第一步取 4，得 6 * 4 * 8 = 192，余下 5 6 8。
//	第二步取 6，得 5 * 6 * 8 = 240，余下 5 8。
//	第三步取 5，得 5 * 8 * 1 = 40，余下 8。
//	最后取 8，得 1 * 8 * 1 = 8 。
//	最终积分为 192 + 240 + 40 + 8 = 480。

class Solution {
    int arr[110] = { 0 };
    int dp[110][110] = { 0 };
public:
    int getCoins(vector<int>& coins) {
        int n = coins.size();
        arr[0] = arr[n + 1] = 1;
        for (int i = 1; i <= n; i++) arr[i] = coins[i - 1];
        for (int i = n; i >= 1; i--) {
            for (int j = i; j <= n; j++) {
                for (int k = i; k <= j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] +
                        arr[i - 1] * arr[k] * arr[j + 1]);
                }
            }
        }
        return dp[1][n];
    }
};